package leetcode;

/**
 * @Classname LongestCommonPrefix0014
 * @Author happytaohaha
 * @Date 2020/3/12
 * @Description 最长公共子串
 */
public class LongestCommonPrefix0014 {

    /**
     * 特殊情况 0个 String
     * while 去比较
     *
     * @param strs
     * @return
     */
    public static String longestCommonPrefix(String[] strs) {
        int len = strs.length;
        if (len == 0) {
            return "";
        }
        StringBuffer stringBuffer = new StringBuffer(strs[0]);
        for (int i = 0; i < strs.length; i++) {
            int len1 = stringBuffer.length() > strs[i].length() ? strs[i].length() : stringBuffer.length();
            int j = 0;
            for (; j < len1; j++) {
                if(stringBuffer.charAt(j)!=strs[i].charAt(j)){
                    break;
                }
            }
            stringBuffer = new StringBuffer(stringBuffer.substring(0,j));
        }
        return stringBuffer.toString();
    }


    /**
     * indexOf 函数 如果包含就返回  0   不包含就返回  -1  或者  1
     * @param strs
     * @Description 跟上面的方法一样 更加的优化
     * O(S)，S 是所有字符串中字符数量的总和。
     * @return
     */
    public String longestCommonPrefix1(String[] strs) {
        if (strs.length == 0) {return "";}
        String prefix = strs[0];
        for (int i = 1; i < strs.length; i++){
            while (strs[i].indexOf(prefix) != 0) {
                prefix = prefix.substring(0, prefix.length() - 1);
                if (prefix.isEmpty()) {return "";}
            }
        }

        return prefix;
    }

    /**
     * 水平扫描  O（S）
     * 想象数组的末尾有一个非常短的字符串，使用上述方法依旧会进行 S​S​ 次比较。优化这类情况的一种方法就是水平扫描。我们从前往后枚举字符串的每一列，先比较每个字符串相同列上的字符（即不同字符串相同下标的字符）然后再进行对下一列的比较。
     * @param strs
     * @return
     */
    public String longestCommonPrefix2(String[] strs) {
        if (strs == null || strs.length == 0) {return "";}
        for (int i = 0; i < strs[0].length() ; i++){
            char c = strs[0].charAt(i);
            for (int j = 1; j < strs.length; j ++) {
                if (i == strs[j].length() || strs[j].charAt(i) != c)
                {return strs[0].substring(0, i);}
            }
        }
        return strs[0];
    }





    public static void main(String[] args) {
        System.out.println("aaaaa".indexOf("aa"));;
    }
}
